import xml.parsers.expat
import sys
import collections

# Generic Stuff
class NodeError(StandardError):
    """Exception raised by Node subclasses when they cannot initialise themselves from attributes supplied."""

class Node:
    OPT_MANDATORY, OPT_OPTIONAL, OPT_MULTI = range(3)      

    # Maps attribute name (also the attribute if the class) to a tuple of (flag, validator). Flag may be one of the 
    #  OPT_MANDATORY or OPT_OPTIONAL, and the validator function returns a value of the correct type or raises an 
    #  exception.
    ATTRIBUTES = {}
    
    # Maps child element name (also the attribute if the class) to a tuple of (flag, validator). Flag may be one of the 
    #  OPT_MANDATORY, OPT_OPTIONAL or OPT_MULTI and the validator function returns a value of the correct type or raises
    #  an exception. If the validator is a class inheriting from Node, then the child's data is read from the XML stream.
    CHILD_ELEMENTS = {}    
    
    # List attribute for content and validator function.
    def _default_content_handler(content):
        if content and not content.isspace():
            raise NodeError("Content illegal for this element.")
    CONTENT = (None, _default_content_handler)
    
    def __init__(self, root, parent, attr):
        "Construct with the given parent and attributes. Raise an exception if things are not well."
        self.root, self.parent = root, parent
        if self.CONTENT[0]:
            setattr(self, self.CONTENT[0], '')
        self.characters = []
        self.simple_attribute = None
        self._check_extra_attributes(attr)
        self._add_attributes(attr)
        self._add_child_element_defaults()
        self._process_child_element_map()
    def _check_extra_attributes(self, attr):
        for k in attr:
            if k not in self.ATTRIBUTES:
                raise NodeError("Extra attribute %s." % k)
    def _add_attributes(self, attr):
        for k, v in self.ATTRIBUTES.items():
            flags, validator = v
            try:
                setattr(self, k, validator(attr[k]))
            except KeyError:
                if flags == Node.OPT_MANDATORY:
                    raise NodeError("Missing attribute `%s`." % k)
                else:
                    setattr(self, k, validator(''))
    def _add_child_element_defaults(self):
        for k, v in self.CHILD_ELEMENTS.items():
            flags, validator = v
            if flags in (Node.OPT_MANDATORY, Node.OPT_OPTIONAL):
                setattr(self, k, None) # We use the presence of the None value to verify that this child is present.
            elif flags == Node.OPT_MULTI:
                setattr(self, k, [])
    def _process_child_element_map(self):
        for k in self.CHILD_ELEMENTS:
            validator_func = self.CHILD_ELEMENTS[k][1]
            if isinstance(validator_func, str):
                self.CHILD_ELEMENTS[k] = self.CHILD_ELEMENTS[k][0], eval(validator_func)
    @classmethod
    def klass(cls):
        return cls.__name__.lower()
    #def __nonzero__(self): return True
    def process_character_data(self, content):
        self.characters.append(content)
    def element_begin(self, name, attrs):
        if self.simple_attribute:
            NodeError("Element %s cannot be nested within element %s." % (name, self.simple_attribute))
        try:
            flags, validator = self.CHILD_ELEMENTS[name]
            # Now decide if we have a subclass (not an _instance_) of Node. Is there a better way to do this?
            try: is_complex_element = issubclass(validator, Node)
            except TypeError: is_complex_element = False
            if is_complex_element: 
                new_child = validator(self.root, self, attrs) # This element's parent is self.
                if flags in (Node.OPT_MANDATORY, Node.OPT_OPTIONAL):
                    if getattr(self, name):
                        raise NodeError("This element may not appear more than once.")
                    else:
                        setattr(self, name, new_child)
                elif flags == Node.OPT_MULTI:
                    getattr(self, name).append(new_child)
                return new_child
            else:
                self.simple_attribute = name
                return None
        except KeyError:
            raise NodeError('Unknown child element %s in node %s' % (name, self.klass()))
    def element_end(self, name):
        if self.simple_attribute:
            if self.simple_attribute != name:
                raise NodeError("Close element for %s unexpected." % name)
            setattr(self, self.simple_attribute, 
              self.CHILD_ELEMENTS[self.simple_attribute][1](self.get_character_data()))
            self.simple_attribute = None
            return False
        elif name != self.klass():
            raise NodeError("Close element for <%s> _really_unexpected, expected <%s>." % (name, self.klass()))
        else:
            self._check_mandatory_present(self.ATTRIBUTES)
            self._check_mandatory_present(self.CHILD_ELEMENTS)
            if self.CONTENT[0]:
                setattr(self, self.CONTENT[0], self.CONTENT[1](self.get_character_data()))
            self.validate()
            return True
    def validate(self):
        "Check that the object is internally consistent after building."
        pass
    def _check_mandatory_present(self, attr_dict):
        for k in [k for (k, v) in attr_dict.items() if v[0] == Node.OPT_MANDATORY]:
            try:
                getattr(self, k)
            except AttributeError:
                raise NodeError("Mandatory attribute %s was not present.")
    def get_character_data(self):
        char_data = ''.join(self.characters)
        self.characters = []
        return char_data
    def __str__(self):        
        strs = []
        self._dump(strs)
        return '\n'.join(strs)
    def _dump(self, strs, depth=1):
        strs.append('  ' * (depth-1) + '<<%s>>' % self.klass())
        all_attrs = [k for k in self.ATTRIBUTES.keys() + [self.CONTENT[0]] + self.CHILD_ELEMENTS.keys() if k]
        for k, val in [(k, getattr(self, k)) for k in all_attrs]:
            if isinstance(val, list):   
                if val and isinstance(val[0], Node):
                    for v in val:
                        v._dump(strs, depth+1)
                else:
                    strs.append('  ' * depth + '%s = `%s`' % (k, val))
            else:
                if isinstance(val, Node):
                    val._dump(strs, depth+1)
                else:
                    strs.append('  ' * depth + '%s = `%s`' % (k, val))
    __repr__ = __str__
    def _toxml(self, ostream, depth=1):
        indent = '  ' * (depth-1)
        ostream.write(indent + '<%s' % self.klass())
        
        # Emit attributes.
        for k in self.ATTRIBUTES:
            v = getattr(self, k)
            assert isinstance(v, str) # ATTRIBUTES are always strings.
            ostream.write(" %s='%s'" % (k, v))
            
        # If this node has no child elements and no content, close the tag now.
        if not self.CHILD_ELEMENTS and not self.CONTENT[0]:  
            ostream.write('/>\n')
        
        else:  # We know that it has either content or child elements.
            ostream.write('>')

            if self.CONTENT[0]:     # Emit content.
                v = getattr(self, self.CONTENT[0])
                if isinstance(v, str):
                    ostream.write(v)
                else:
                    ostream.write(' '.join(v)) # Assume some sort of sequence.
                
            # Emit attributes.
            if self.CHILD_ELEMENTS: # New line for child elements.
                ostream.write('\n')
                for k in self.CHILD_ELEMENTS:
                    v = getattr(self, k)
                    if v is None:
                        ostream.write(indent + '  <%s/>\n' % k)
                    elif isinstance(v, str):
                        ostream.write(indent + '  <%s>%s</%s>\n' % (k, v, k))
                    elif isinstance(v, Node):
                        v._toxml(ostream, depth+1)
                    elif isinstance(v, list):
                        for n in v:
                            n._toxml(ostream, depth+1)
                    else:
                        ostream.write(indent + '  <%s>%s</%s>\n' % (k, ' '.join(v), k)) # Assume some sort of sequence.
                        
                ostream.write(indent + '</%s>\n' % self.klass())
            else:
                ostream.write('</%s>\n' % self.klass())

class XmlSerialiser:
    """A cheesy little xml serialiser/deserialiser."""
    def __init__(self, root_type):
        self.xml_parser = xml.parsers.expat.ParserCreate()
        self.xml_parser.StartElementHandler = self.start_element
        self.xml_parser.EndElementHandler = self.end_element
        self.xml_parser.CharacterDataHandler = self.process_character_data
        self.current = None
        self.root_type = root_type
    def start_element(self, name, attrs):
        str_attrs = dict([(str(k), str(v)) for(k, v) in attrs.items()])
        str_name = str(name)
        if self.current is None:
            if self.root_type.klass() == str_name:
                self.current = self.root_type(None, None, str_attrs) 
                self.current.root = self.current
            else:
                raise NodeError("Unknown root element: %s" % str_name)
        else:
            new_child = self.current.element_begin(str(str_name), str_attrs)
            if new_child:
                self.current = new_child
    def end_element(self, name):
        str_name = str(name)
        t = self.current.element_end(str_name)
        if t and self.current.parent:
            self.current = self.current.parent
    def process_character_data(self, content):
        self.current.process_character_data(str(content))
    def parse(self, s):
        self.xml_parser.Parse(s, 1)

# SMK Parser Stuff.
def normalise_code(text):
    return '\n'.join([y for y in text.strip().splitlines() if y and not y.isspace()])
def mk_set(text):
    return set(text.split())
def validate_name(n):
    n = n.strip()
    if not n:
        raise NodeError("A Node must have a legal name")
    return n    
class Init(Node):
    CONTENT = ('action', lambda n: n.strip())
    ATTRIBUTES = {'target': (Node.OPT_MANDATORY, validate_name)}
    def __init__(self, *args): Node.__init__(self, *args)
class History(Init):
    def __init__(self, *args): Init.__init__(self, *args)
class Entry(Node):
    CONTENT = ('action', lambda n: n.strip())
    def __init__(self, *args): Node.__init__(self, *args)
class Exit(Entry):
    def __init__(self, *args): Entry.__init__(self, *args)
class Transition(Node):
    CONTENT = ('action', lambda n: n.strip())
    ATTRIBUTES = {
      'event': (Node.OPT_MANDATORY, validate_name),
      'target': (Node.OPT_OPTIONAL, lambda n: n.strip()),
      'guard': (Node.OPT_OPTIONAL, lambda n: n.strip()),
    }
    def __init__(self, *args): 
        Node.__init__(self, *args)
    def validate(self):
        if self.root.event_list and self.event not in self.root.event_list:
            raise NodeError("Explicit event list given and event %s was not present." % self.event)
        self.root.events[self.event] = None

        # Verify target state is present in explicit state list if it is given.
        if self.root.state_list and self.target and self.target not in self.root.state_list:
            raise NodeError("Explicit state list given and target state %s was not found." % self.target)
            
        # Check for an internal transition with no action, probably a miss steak.
        if not self.target and not self.action:
            raise NodeError("Degenerate transition %s does nothing", self)

class NodeWithInitTransition(Node):
    def get_superstates(self):
        s = [self]
        while s[-1].parent:
            s.append(s[-1].parent)
        return s
    def get_init_actions_state(self): 
        "Return tuple (list of init/entry actions, destination_state) for the given node (Machine or State)."
        action_nodes = []
        node = self
        
        # Do init actions until we reach a substate with no init transition.
        while node.init:
            action_nodes.append(node.init)
            n = node.root.state_map[node.init.target]
            nodes_entered = []
            while n.name != node.name:
                nodes_entered.insert(0, n.entry)
                n = n.parent
            node = node.root.state_map[node.init.target]
            action_nodes += nodes_entered

        return [a.action for a in action_nodes if a], node # Remove all empty actions.
            
class State(NodeWithInitTransition): 
    ATTRIBUTES = {
      'name': (Node.OPT_MANDATORY, validate_name),
    }
    CHILD_ELEMENTS = {
      'init': (Node.OPT_OPTIONAL, Init),
      'history': (Node.OPT_OPTIONAL, History), # History & Init cannot occur together.
      'entry': (Node.OPT_OPTIONAL, Entry),
      'exit': (Node.OPT_OPTIONAL, Exit),
      'transition': (Node.OPT_MULTI, Transition),
      'state': (Node.OPT_MULTI, "State"), # Allow States to contain States.
    }
    def __init__(self, root, parent, attrs):
        Node.__init__(self, root, parent, attrs)

        # Add to the root's state map, which is the primary data structure.
        if self.name in self.root.state_map:
            raise NodeError("Duplicate state name %s." % self.name)
        self.root.state_map[self.name] = self
    def validate(self):
        # Verify name is present in explicit state list.
        if self.root.state_list and self.name not in self.root.state_list:
            raise NodeError("Explicit state list given and state %s was not present." % self.name)
        
        # Verify that all transition have distinct event signatures.
        # For free this also verifies that at most one transition for each event has no guard.
        trans = set()
        for t in self.transition:
            trans_sig = (t.event, t.guard)
            if trans_sig in trans:
                raise NodeError("Transition with signature %s[%s] duplicated." % (t.event, t.guard))
            else:
                trans.add(trans_sig)
#            if not t.action and t.target == self.name:
#                raise NodeError("Self transition with signature %s[%s] has no action." % (t.event, t.guard))
                
		
		# Verify that if this state has an initial transition, the transition targets a substate.
        if self.init:
            if self.init.target == self.name:
                raise NodeError("Initial transition cannot target self")
            try: 
                n = self.root.state_map[self.init.target]
            except KeyError: 
                raise NodeError("Initial transition targeted an unknown state %s." % self.init.target)
            while n:
                if n.name == self.name:
                    break
                n = n.parent
            if n is None:
                raise NodeError("Initial transition targeted a non-substate %s." % self.init.target)
        
        # Verify that history & init are not both present.
        if self.init and self.history:        
            raise NodeError("Cannot have an initial transition and a history in the same state %s." % self.name)
        
class Options(Node):
    CONTENT = ('content', lambda x: set([k for k in x.lower().split()]))
    def __init__(self, *args): Node.__init__(self, *args)
     
class Machine(NodeWithInitTransition): 
    ATTRIBUTES = {
      'name': (Node.OPT_MANDATORY, validate_name),
    }
    strip = lambda s: s.strip()
    CHILD_ELEMENTS = {
      'state_list': (Node.OPT_OPTIONAL, mk_set),
      'event_list': (Node.OPT_OPTIONAL, mk_set),
      'property_list': (Node.OPT_OPTIONAL, strip),
      'log': (Node.OPT_OPTIONAL, strip),
      'include': (Node.OPT_OPTIONAL, strip),
      'code': (Node.OPT_OPTIONAL, strip),
      'options': (Node.OPT_OPTIONAL, Options),
      'init': (Node.OPT_OPTIONAL, Init),
      'state': (Node.OPT_MULTI, State),
    }
    def __init__(self, root, parent, attrs):
        Node.__init__(self, None, None, attrs)
        
        # We build a list in the machine of all states as we parse the input, allows us to detect duplicated states.
        self.state_map = collections.OrderedDict()

        # Set of events encountered, used to validate events missing from event list. We really want an ordered set.
        self.events = collections.OrderedDict()
        
    def validate(self):
        # Verify that all states listed in the explicit state list have been defined.
        if self.state_list:
            undefined_states = self.state_list - set(self.state_map.keys())
            if undefined_states:
                raise NodeError("The following states were not defined: %s." % ', '.join(undefined_states))

        # Verify that all events listed in the explicit event list have been used.
        if self.event_list:
            undefined_events = self.event_list - set(self.events)
            if undefined_events:
                raise NodeError("The following events were not used: %s." % ', '.join(undefined_events))
                        
        # Add an event list if one was not supplied explicitly.
        if not self.event_list:
            self.event_list = set(self.events)

        # Verify target state for all transitions. We do this even if an explicit state list is defined, as 
        #  transitions can be defined before the explicit state list is defined in which case they would not be checked.
        for state in self.state_map.values():
            for trans in state.transition:
                if trans.target and trans.target not in self.state_map:        # Internal transitions have a nil target.
                    raise NodeError("Target state %s for State %s transition %s[%s] was not present." % 
                      (trans.target, state.name, trans.event, trans.guard))

        # Add an initial transition if possible, else abort.
        if not self.init:
            if len(self.state) == 1:
                self.init = Init(self, self, {'target': self.state[0].name})
            elif len(self.state) > 1:
                raise NodeError("Machine %s has no initial transition specified on reset." % self.name)
		
        # Verify that if this state has an initial transition, it targets a substate.
        # TODO: share code with State.
        if self.init:
            try: n = self.root.state_map[self.init.target]
            except KeyError: raise NodeError("Initial transition for Machine targeted an unknown state %s." % 
              self.init.target)

def parse(s):
    p = XmlSerialiser(Machine)
    p.parse(s)
    return p.current
            
if __name__ == '__main__':            
    print parse(open(sys.argv[1], 'rt').read())


